#include "log.h"
#include "myfuse.h"
#include "libgen.h"

FILE * logfile = NULL;		//log file used for debugging
FILE * fusefile = NULL; 	//fuse file used for saving the entire file system when unmounting the file system
inode_t * root = NULL;		//the inode of the root (mountpoint)

//the maximum inode id in current inode_table
//this variable is used to calcuate the next available inode id
static int max_inode_id = -1;

//get the next available inode id given the current maximum inode id
int __get_available_id()
{
	return ++max_inode_id;
}

//find the maximum inode id by
//traversing the whole inode table
int __find_max_inode_id()
{
	int max = -1;
	for(auto i = inode_table.begin(); i != inode_table.end(); ++i)
	{
		if ((*i)->id > max)
			max = (*i)->id;
	}
	return max;
}

//get count number of free blocks
//return the index of the first block
//or return -1 if error
int get_free_blocks(int count)
{
	log_msg("\n==>get_free_blocks = %d\n", count);

	int size = blocks.size();
	if(count <= 0)
		return -1;

	int first = -1;
	block_t * prev = NULL;

	int i = 0;
	for(i = 0; i < size; ++i)
	{
		if(blocks[i]->valid == 0)		//this block is free
		{
			blocks[i]->next = -1;		
			blocks[i]->valid = 1;		//mark this block as occupied
	
			//if this block has precedent, link them		
			if(prev)			
				prev->next = i;

			//set the first block
			if (first == -1)
				first = i;
			

			prev = blocks[i];
			count--;
			if(count == 0)
				break;
		}
	}

	//we need more blocks, but current allocated blocks are not enough
	//so we need to malloc some new blocks and return these bloks together
	//with the free blocks we have found in the previous loop.
	if(count > 0)
	{
		while(count)
		{
			//allocate another new block
			block_t * blk = (block_t *)malloc(sizeof(block_t));

			//init the new allocated block
			memset(blk->data, 0, sizeof(char)*BLOCK_SIZE);
			blk->next = -1;
			blk->valid = 1;

			//set the next field of the previous block
			if(prev)
				prev->next = blocks.size();

			//set the first block pointer if necessary
			if(first == -1)
				first = blocks.size();
	
			//put this new allocated block into the container
			blocks.push_back(blk);
			count--;
		}
	}
	
	log_msg("\n<==get_free_blocks = %d, first = %d\n", count, first);

	for(int i = first; i != -1; i = blocks[i]->next)
		log_msg("%d ", i);
	log_msg("\n");

	return first;
}

// Returns a pointer to the first character of the last directory entry
// in the given path.
// [mfs] need to stop needing this...
const char* get_filename (const char* path)
{
    const char* p;
    if ((p = strrchr(path,'/')) == 0)
        return 0;
    return p+1;
}

/**
 *  Helper function for managing permissions
 *  [mfs] this might not always be doing the right thing ;)
 */
mode_t my_rights(struct stat* stbuf, uid_t uid, gid_t gid)
{
    mode_t rights = 0;
    rights |= stbuf->st_mode & 7;
    if (stbuf->st_uid == uid)
        rights |= (stbuf->st_mode >> 6) & 7;
    if (stbuf->st_gid == gid)
        rights |= (stbuf->st_mode >> 3) & 7;
    return rights;
}


//get a list of path conponents by parsing the path
void parse_path(vector<string> * paths, const char* path)
{
      	log_msg("\n==>parse_path path = \"%s\")\n", path);

	stack<string> reverse_paths;

	char tmp_path[MAX_NAME_LEN], *prefix, *base, *path1, *path2;
	strcpy(tmp_path, path);

	//this loop gets path components one by one, from the rightmost component to the leftmost component '/'
	do
	{
		path1 = strdup(tmp_path);
		path2 = strdup(tmp_path);
		prefix = dirname(path1);
		base = basename(path2);
		
		reverse_paths.push(string(base));
		
		if(strcmp(prefix, base) == 0 && (strcmp(base, "/") == 0 || strcmp(base, ".") == 0))
			break;
		strcpy(tmp_path, prefix);
	}while(1);

      
	log_msg("\nparsed Path:\n");
	
	//pop all the components and put them into the paths container in the correct order
	while(!reverse_paths.empty())
	{
		paths->push_back(reverse_paths.top());
		log_msg("%s ", reverse_paths.top().c_str());
		reverse_paths.pop();
	}
	log_msg("\n<==parse_path path = \"%s\"\n", path);
}

/*this function parses the content of the directory dir and put the names of all its children - files or subdirectories - into the vector dentries*/
void parse_dentry(vector<string> * dentries, inode_t * dir)
{
	log_msg("\n==> parse dentry, dir = \"%s\"\n", dir->name);
	log_msg("dir content: %s\n", blocks[dir->blk_start]->data);

	//this loop currently runs only *once*, since by default directories can only have one block
	//this might be extended in the future
	for(int i = dir->blk_start; i != -1; i = blocks[i]->next)
	{
		block_t * blk = blocks[i];
		assert(blk);
		
		char buffer[BLOCK_SIZE] = {0};
		strcpy(buffer, blk->data);

		char * dentry = NULL;
		dentry = strtok(buffer, "\n");

		//get one dentry string in each loop
		while(dentry)
		{
			dentries->push_back(string(dentry));
			dentry = strtok(NULL, "\n");
		}
	}

	log_msg("\n<==parse_dentry, dir = \"%s\"\n", dir->name);
}

//get the pointer to the inode structure given the inode id
inode_t * get_inode(int inode_id)
{
	log_msg("\n==>get_inode, id = \"%d\"\n", inode_id);
	
	inode_t * inode = NULL;
	
	//find this id in the dentry cache
	//if found, return this inode
	//if not, find this inode in the inode_table
	//and put this inode in the dentry cache so that
	//next time we will get this inode only by accessing dentry cache
	//without having to traverse the inode table
	if(dentry_cache.find(inode_id) != dentry_cache.end())	//found this entry in the cache
		inode = dentry_cache[inode_id];
	else
	{

		vector<inode_t *>::iterator i, j;
		for (i = inode_table.begin(), j = inode_table.end(); i != j; ++i)
		{
			if ((*i)->id == inode_id)
			{
				dentry_cache[inode_id] = *i;
				inode = *i;
				break;
			}
		}
	}

	log_msg("\n<==get_inode, id = \"%d\", inode = \"%p\"\n", inode_id, inode);
	return inode;
}
//get the inode of a centain dentry string, note that this function 
//restrains that only one dentry name, file name or directory name, 
//can exist in a given parent inode. So it's impossible to create two
//dentries with the same name in one parent inode 

//input: 	the parent inode of this dentry string
//	 	the dentry string
//output: 	the inode of this dentry
inode_t * get_inode(inode_t * parent, const char * inode_name)
{
      	log_msg("\nget_inode name=\"%s\"\n", inode_name);

	if(parent == NULL)	//only the root's parent is NULL
	{
		assert(strcmp(inode_name, "/") == 0);
		assert(root);
		return root;
	}

	string name(inode_name);

	vector<inode_t *>::iterator i, j;
	for (i = inode_table.begin(), j = inode_table.end(); i != j; ++i)
	{
		//we ensure that the name is the one we would like to find
		//and the parent of this dentry name also matches the one
		//we would like to find
		if ((*i)->name == name && (*i)->parent == parent->id)
		{
			return *i;
		}
	}

	return NULL;
}

                
//find the inode given the absolute path of this inode
inode_t * find_inode(const char* path)
{
      	log_msg("\n==>find_inode path = \"%s\"\n", path);
	
	vector<string> paths;
	parse_path(&paths, path);
	assert(strcmp(paths.begin()->c_str(), "/") == 0);

	inode_t * parent = NULL;

	//for each path component, we look up its sub path component deeper
	//and deeper, and finally find the correct inode if it exists
	//or NULl if it does not exist.
	for(auto p = paths.begin(); p != paths.end(); ++p)
	{
		inode_t * n = NULL;
		string name = *p;

		//this inode does not exist
		if((n = get_inode(parent, name.c_str())) == NULL)
		{
			log_msg("<==find_inode: cannot find inode for name '%s'\n", name.c_str());
			return NULL;
		}
		assert(n);

		//this inode is neither a file inode or directory inode
		//currently, this situation is not supported
		if(!S_ISDIR(n->stbuf.st_mode) && !S_ISREG(n->stbuf.st_mode))
		{
			log_msg("<==find_inode: '%s' is neither a regular file nor a directory file!");
			return NULL;
		}
		
		//this is a regular file
		if(S_ISREG(n->stbuf.st_mode))
		{
			log_msg("<==find_inode, inode = %p\n", n);
			return n;
		}
		
		//this is the last entry
		if(p+1 == paths.end())
		{
			log_msg("<==find_inode, inode = %p\n", n);
			return n;
		}
		else	//this is a directory and not the last entry
		{
			vector<string> dentries;
			parse_dentry(&dentries, n);
	
			vector<string>::iterator de;
			for(de = dentries.begin(); de != dentries.end(); ++de)
			{
				if (strcmp((p+1)->c_str(), de->c_str()) == 0)
					break;
			}

			if (de == dentries.end())
			{	
				log_msg("<==find_inode: directory '%s' does not exist!\n", (p+1)->c_str());
				return NULL;
			}
			else
			{
				//have finished this round of loop, set the parent as the current inode
				//and start the next round of loop
				parent = n;
				continue;
			}
		}
	}

	log_msg("<==find_inode Error: should not reach here!\n");
	return NULL;
}

//get the absolute parent path given a path
char * parent_path(const char * path)
{
	char tmp_path[MAX_NAME_LEN], *prefix, *path1;
	strcpy(tmp_path, path);
	
	path1 = strdup(tmp_path);
	prefix = dirname(path1);

	return prefix;
}

//add a dentry string to the last of directory block whose inode is indicated as dir
void add_dentry(inode_t * dir, const char * entry)
{
	int i;

	//find the end of the directory blocks
	//currently this loop will not take effect because we assume that 
	//each directory has no more than 1 data block
	for(i = dir->blk_start; blocks[i]->next != -1; i = blocks[i]->next)
		;

	strcat(blocks[i]->data, entry);
	strcat(blocks[i]->data, "\n");
}

//remove a dentry string from the directory block whose inode is indicated as dir
int remove_dentry(inode_t * dir, const char * entry)
{
	log_msg("\n==> remove dentry, dir = \"%s\", entry = \"%s\"\n", dir->name, entry);
	log_msg("dir content: %s\n", blocks[dir->blk_start]->data);

	for(int i = dir->blk_start; i != -1; i = blocks[i]->next)
	{
		block_t * blk = blocks[i];
		assert(blk);
		
		char buffer[BLOCK_SIZE] = {0};
		strcpy(buffer, blk->data);

		memset(blk->data, 0, BLOCK_SIZE);
		char * dentry = NULL;
		dentry = strtok(buffer, "\n");
		while(dentry)
		{
			if(strcmp(dentry, entry) != 0)
			{
				strcat(blk->data, dentry);
				strcat(blk->data, "\n");
			}
			dentry = strtok(NULL, "\n");
		}

		log_msg("\n%s\n", blk->data);
		log_msg("\n<==remove_dentry = 0, dir = \"%s\"\n", dir->name);
		return 0;
	}

	log_msg("\n<==remove_dentry = -1, dir = \"%s\"\n", dir->name);
	return -1;
}
/**
 *  For debugging, to get you started with figuring out why root permissions
 *  are funny
 */
void info()
{
	uid_t a = getuid(), b = geteuid(), c = getgid(), d = getegid();
	cerr << "uid, euid, gid, egid = "
		<< a << ", "
		<< b << ", "
		<< c << ", "
		<< d << endl;
}

/* show usage of this file system */
void usage()
{
	fprintf(stderr, "usage: myfuse [FUSE and mount options] mountPoint");	
	abort();
}

/**
 *  Get attributes
 */
int myfs_getattr(const char* path, struct stat* stbuf)
{
	log_msg("\n==>getattr path = \"%s\", statbuf = 0x%08x\n", path, stbuf);

	if (string(path) == "/") {
		memcpy(stbuf, &root->stbuf, sizeof(struct stat));
	}
	else {
		//find this inode first, then do the job
		inode_t* file = find_inode(path);
		if (NULL == file)
			return -ENOENT;
		memcpy(stbuf, &file->stbuf, sizeof(struct stat));
	}
	
	log_msg("\n<==getattr path = \"%s\", statbuf = 0x%08x\n", path, stbuf);
	return 0;
}

/**
 *  Man 3 truncate suggests this is not a conforming implementation
 */
int myfs_truncate(const char* path, off_t size)
{
	log_msg("\n==>truncate, path = \"%s\"\n", path);
	if (size > BLOCK_SIZE)
		return -EIO;

	//find this inode first, then do the job
	inode_t* file = find_inode(path);
	if (file == NULL)
		return -ENOENT;

	fuse_context* context = fuse_get_context();
	mode_t rights = my_rights(&file->stbuf, context->uid, context->gid);
	if (!(rights & 2))
		return -EACCES;

	file->stbuf.st_size = 0;
	
	log_msg("\n<==truncate, path = \"%s\"\n", path);
	return 0;
}

/**
 *  Rename: not safe once we have more folders
 */
int myfs_rename(const char* from, const char* to)
{
	log_msg("\n==>rename, from = \"%s\", to = \"%s\"\n", from, to);

	//find this inode first, then do the job
	fuse_context* context;
	inode_t* file = find_inode(from);

	if (file == NULL)
		return -ENOENT;
	context = fuse_get_context();
	if (file->stbuf.st_uid != context->uid)
		return -EACCES;

	//get the inode of the parent	
	inode_t * from_parent = get_inode(file->parent);
	//remove this file dentry string from the parent file
	remove_dentry(from_parent, file->name);
	
	//find the parent string of the to string
	char * parent = NULL;
	parent = parent_path(to);
	log_msg("to's parent: %s\n", parent);
	
	//find this inode first, then do the job
	inode_t * to_parent = find_inode(parent);

	//change the inode actual name
	strcpy(file->name, get_filename(to));

	//add this file name to the parent 
	add_dentry(to_parent, file->name);
	file->parent = to_parent->id;
	
	log_msg("\n<==rename, from = \"%s\", to = \"%s\"\n", from, to);
	return 0;
}


/**
 *  This won't be correct once hard links are supported
 */
int myfs_unlink(const char* path)
{
	log_msg("\n==>unlink, path = \"%s\"\n", path);
	
	fuse_context* context;
	inode_t* file;
	file = find_inode(path);
	if (file == NULL)
		return -ENOENT;

	context = fuse_get_context();
	if (file->stbuf.st_uid != context->uid)
		return -EACCES;

	//if link > 1, decrease link and return
	//else
	
	for (int i = file->blk_start; i != -1; i = blocks[i]->next)
		blocks[i]->valid = 0;			//mark this block as free

	inode_t * parent = get_inode(file->parent);
	remove_dentry(parent, file->name);

	vector<inode_t *>::iterator i;
	for(i = inode_table.begin(); i != inode_table.end(); ++i)
	{
		if((*i)->id == file->id)
		{
			inode_table.erase(i);
			free(file);
			break;
		}
	}
	
	log_msg("\n<==unlink, path = \"%s\"\n", path);
	return 0;
}

/**
 *  Example of how to set time
 */
int myfs_utime(const char* path, struct utimbuf* buf)
{
	log_msg("\n==>utime, path = \"%s\"\n", path);

	fuse_context* context;
	inode_t* file;

	file = find_inode(path);
	if (file == NULL)
		return -ENOENT;

	context = fuse_get_context();
	if (buf != 0) {
		if (context->uid != 0 && file->stbuf.st_uid != context->uid)
			return -EPERM;
		file->stbuf.st_atime = file->stbuf.st_mtime = time(0);
	}
	else {
		mode_t rights = my_rights(&file->stbuf, context->uid, context->gid);
		if (context->uid != 0 && file->stbuf.st_uid != context->uid
				&& !(rights & 2))
		{
			return -EACCES;
		}
		file->stbuf.st_atime = buf->actime;
		file->stbuf.st_mtime = buf->modtime;
	}

	log_msg("\n<==utime, path = \"%s\"\n", path);
	return 0;
}

/*change the read/write/execute permission of a file or directory */
int myfs_chmod(const char *path, mode_t mode)
{
	log_msg("\n==>myfs_chmod, path = \"%s\"\n", path);

	fuse_context* context;
	inode_t* file;

	file = find_inode(path);
	if (file == NULL)
		return -ENOENT;

	context = fuse_get_context();
	
	mode_t rights = my_rights(&file->stbuf, context->uid, context->gid);
	if (context->uid != 0 && file->stbuf.st_uid != context->uid
			&& !(rights & 2))
	{
		return -EACCES;
	}

	file->stbuf.st_mode = mode;
	log_msg("\n<==myfs_chmod, path = \"%s\"\n", path);
	return 0;
}

/*change the owner of a file or directory */
int myfs_chown(const char *path, uid_t uid, gid_t gid)
{
	log_msg("\n==>myfs_chmod, path = \"%s\"\n", path);
	
	fuse_context* context;
	inode_t* file;

	file = find_inode(path);
	if (file == NULL)
		return -ENOENT;

	context = fuse_get_context();
	
	mode_t rights = my_rights(&file->stbuf, context->uid, context->gid);
	if (context->uid != 0 && file->stbuf.st_uid != context->uid
			&& !(rights & 2))
	{
		return -EACCES;
	}

	file->stbuf.st_uid = uid;
	file->stbuf.st_gid = gid;
	log_msg("\n<==myfs_chmod, path = \"%s\"\n", path);
	return 0;
}

/**
 *  Write to a file
 */
int myfs_write(const char* path, const char* buf, size_t size,
               off_t offset, fuse_file_info* fi)
{
	log_msg("\n==>write, path = \"%s\"\n", path);
//	log_fi(fi);
	
	inode_t* file = (inode_t *)fi->fh;
	assert(file);
	
//	log_msg("buf:%s\n", buf);
	log_msg("size: %u\n", size);
	log_msg("offset: %d\n", offset);

	//we only need to write to no more than one block	
	if(size <= size_t(BLOCK_SIZE - offset%BLOCK_SIZE))
	{
		log_msg("write only one page\n");
		int starter = file->blk_start;
		int hop = offset/BLOCK_SIZE;
		int prev = -1;

		//find that block
		for(; starter != -1 && hop; starter = blocks[starter]->next, hop--)
		{
			prev = starter;
			log_msg("->[block:%d, next:%d, hop:%d]", starter, blocks[starter]->next, hop);
		}
		log_msg("\n");

		if(starter == -1 && hop)	
		{
			//we still have hops, but we run out of effective blocks....
			//so we need to allocate more blocks for this file
			//and continue our remaining hops...
			int new_start = get_free_blocks(hop + 1);
			blocks[prev]->next = new_start;
			for(starter = new_start; starter != -1 && hop; starter = blocks[starter]->next, hop--)
				;
			if(starter == -1)
			{
				log_msg("Write Error!\n");
				return -EIO;
			}
			
			log_msg("write block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, size);
			memcpy(&blocks[starter]->data[offset%BLOCK_SIZE], buf, size);
		}
		else if(starter == -1 && !hop)
		{
			int new_start = get_free_blocks(1);
			blocks[prev]->next = new_start;
			log_msg("write block:%d, offset:%d, size:%d\n", new_start, offset%BLOCK_SIZE, size);
			memcpy(&blocks[new_start]->data[offset%BLOCK_SIZE], buf, size);
		}
		else if(starter != -1 && !hop)
		{
			log_msg("write block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, size);
			memcpy(&blocks[starter]->data[offset%BLOCK_SIZE], buf, size);
		}
	}
	else
	{
		log_msg("write multiple pages\n");
		size_t remain = size;
		const char * pos = buf;

		int starter = file->blk_start;
		int hop = offset/BLOCK_SIZE;
		int prev = -1;

		for(; starter != -1 && hop; starter = blocks[starter]->next, hop--)
		{
			log_msg("->[block:%d, next:%d, hop:%d]", starter, blocks[starter]->next, hop);
			prev = starter;
		}
		log_msg("\n");

		if(starter == -1 && hop)
		{
			//we still have hops, but we run out of effective blocks....
			//so we need to allocate more blocks for this file
			//and continue our remaining hops...
			int new_start = get_free_blocks(hop + 1);
			blocks[prev]->next = new_start;
			for(starter = new_start; starter != -1 && hop; starter = blocks[starter]->next, hop--)
				;
			if(starter == -1)
			{
				log_msg("Write Error!\n");
				return -EIO;
			}
		
			log_msg("write block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, BLOCK_SIZE - offset%BLOCK_SIZE);
			memcpy(&blocks[starter]->data[offset%BLOCK_SIZE], pos, BLOCK_SIZE - offset%BLOCK_SIZE);
		}
		else if(starter == -1 && !hop)
		{
			int new_start1 = get_free_blocks(1);
			blocks[prev]->next = new_start1;
			log_msg("write block:%d, offset:%d, size:%d\n", new_start1, offset%BLOCK_SIZE, BLOCK_SIZE - offset%BLOCK_SIZE);
			memcpy(&blocks[new_start1]->data[offset%BLOCK_SIZE], pos, BLOCK_SIZE - offset%BLOCK_SIZE);
		}
		else if(starter != -1 && !hop)
		{

			log_msg("write block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, BLOCK_SIZE - offset%BLOCK_SIZE);
			memcpy(&blocks[starter]->data[offset%BLOCK_SIZE], pos, BLOCK_SIZE - offset%BLOCK_SIZE);
		}
		
		remain -= BLOCK_SIZE - offset%BLOCK_SIZE;
		pos += BLOCK_SIZE - offset%BLOCK_SIZE;

		int new_start = get_free_blocks(remain/BLOCK_SIZE + 1);
		for(; blocks[starter]->next != -1; starter = blocks[starter]->next)
			;
		blocks[starter]->next = new_start;

		for(int sb = new_start; sb != -1; sb = blocks[sb]->next)
		{
			size_t copy_size = (remain > BLOCK_SIZE)? BLOCK_SIZE : remain;

			log_msg("write block:%d, offset:%d, size:%d\n", sb, 0, copy_size);
			memcpy(blocks[sb]->data, pos, copy_size);
			pos += copy_size;
			remain -= copy_size;
		}
	}	
	

	int diff = offset + size - file->stbuf.st_size;
	if (diff > 0) {
		file->stbuf.st_size += diff;
		file->stbuf.st_blocks = 1;
	}

//	log_msg("file content written:\n==========\n");
//	for(int i = file->blk_start; i != -1; i = blocks[i]->next)
//		log_msg("%s", blocks[i]->data);
//	log_msg("\n==========\n");

	log_msg("\n<==write, path = \"%s\"\n", path);
	return size;
}

/**
 *  Read from a file
 */
int myfs_read(const char* path, char* buf, size_t size,
              off_t offset, fuse_file_info* fi)
{
	log_msg("\n==>read, path = \"%s\"\n", path);
//	log_fi(fi);
	
	inode_t * file = (inode_t *)fi->fh;
	assert(file);

	log_msg("size: %u\n", size);
	log_msg("offset: %d\n", offset);

	if(size <= size_t(BLOCK_SIZE - offset%BLOCK_SIZE))
	{
		log_msg("read only one page.\n");
		int starter = file->blk_start;
		int hop = offset/BLOCK_SIZE;
		int prev = -1;

		for(; starter != -1 && hop; starter = blocks[starter]->next, hop--)
		{
			prev = starter;
			log_msg("->[block:%d, next:%d, hop:%d]", starter, blocks[starter]->next, hop);
		}
		log_msg("\n");
		if(starter == -1 && hop)
		{
			int new_start = get_free_blocks(hop + 1);
			blocks[prev]->next = new_start;
			for(starter = new_start; starter != -1 && hop; starter = blocks[starter]->next, hop--)
				;
			if(starter == -1)
			{
				log_msg("Read Error!\n");
				return -EIO;
			}
		
			log_msg("read block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, size);
			memcpy(buf, &blocks[starter]->data[offset%BLOCK_SIZE], size);
		}
		else if (starter == -1 && !hop)
		{
			int new_start1 = get_free_blocks(1);
			blocks[prev]->next = new_start1;
			log_msg("read block:%d, offset:%d, size:%d\n", new_start1, offset%BLOCK_SIZE, size);
			memcpy(buf, &blocks[new_start1]->data[offset%BLOCK_SIZE], size);
		}
		else if (starter != -1 && !hop)
		{
			log_msg("read block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, size);
			memcpy(buf, &blocks[starter]->data[offset%BLOCK_SIZE], size);
		}
	}
	else
	{
		log_msg("need to read multiple pages.\n");
		size_t remain = size;
		char * pos = buf;

		int starter = file->blk_start;
		int hop = offset/BLOCK_SIZE;
		int prev = -1;
		
		for(; starter != -1 && hop; starter = blocks[starter]->next, hop--)
		{
			prev = starter;
			log_msg("->[%d,%d, hop:%d]", starter, blocks[starter]->next, hop);
		}
		log_msg("\n");
		if(starter == -1 && hop)
		{
			int new_start = get_free_blocks(hop + 1);
			blocks[prev]->next = new_start;
			for(starter = new_start; starter != -1 && hop; starter = blocks[starter]->next, hop--)
				;
			if(starter == -1)
			{
				log_msg("Read Error!\n");
				return -EIO;
			}
		
			log_msg("read block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, BLOCK_SIZE - offset%BLOCK_SIZE);
			memcpy(pos, &blocks[starter]->data[offset%BLOCK_SIZE], BLOCK_SIZE - offset%BLOCK_SIZE);
		}
		else if (starter == -1 && !hop)
		{
			int new_start1 = get_free_blocks(1);
			blocks[prev]->next = new_start1;

			log_msg("read block:%d, offset:%d, size:%d\n", new_start1, offset%BLOCK_SIZE, BLOCK_SIZE - offset%BLOCK_SIZE);
			memcpy(pos, &blocks[new_start1]->data[offset%BLOCK_SIZE], BLOCK_SIZE - offset%BLOCK_SIZE);
		}
		else if (starter != -1 && !hop)
		{
			log_msg("read block:%d, offset:%d, size:%d\n", starter, offset%BLOCK_SIZE, BLOCK_SIZE - offset%BLOCK_SIZE);
			memcpy(pos, &blocks[starter]->data[offset%BLOCK_SIZE], BLOCK_SIZE - offset%BLOCK_SIZE);
		}
		remain -= BLOCK_SIZE - offset%BLOCK_SIZE;
		pos += BLOCK_SIZE - offset%BLOCK_SIZE;

		for(int sb = blocks[starter]->next; sb != -1; sb = blocks[sb]->next)
		{
			size_t copy_size = (remain > BLOCK_SIZE)? BLOCK_SIZE : remain;
			log_msg("read block:%d, offset:%d, size:%d\n", sb, 0, copy_size);
			memcpy(pos, blocks[sb]->data, copy_size);
			pos += copy_size;
			remain -= copy_size;
		}
	}
	
//	log_msg("buf content:\n%s\n", buf);
	log_msg("\n<==read, path = \"%s\"\n", path);
	return size;
}

/**
 *  Make a new entry in the filesystem
 */
int myfs_mknod(const char* path, mode_t mode, dev_t dev)
{
	log_msg("\n==>mknod, path = \"%s\"\n", path);

	fuse_context* context = fuse_get_context();

	inode_t* newfile = (inode_t *)malloc(sizeof(inode_t));
	if(!newfile)
		return -ENOMEM;

	newfile->id = __get_available_id();
	strcpy(newfile->name, get_filename(path));

	memset(&newfile->stbuf, 0, sizeof(struct stat));
	newfile->stbuf.st_mode = mode;
	newfile->stbuf.st_dev = dev;
	newfile->stbuf.st_nlink = 1;

	newfile->stbuf.st_atime = newfile->stbuf.st_mtime =
	newfile->stbuf.st_ctime = time(0);
	newfile->stbuf.st_uid = context->uid;
	newfile->stbuf.st_gid = context->gid;
	newfile->stbuf.st_blksize = BLOCK_SIZE;
	
	newfile->blk_start = get_free_blocks(1);
	inode_table.push_back(newfile);

	char * parent = NULL;
	parent = parent_path(path);
	log_msg("parent: %s\n", parent);
		
	inode_t * parent_inode = find_inode(parent);
	add_dentry(parent_inode, newfile->name);

	newfile->parent = parent_inode->id;
	log_msg("\n<==mknod, path = \"%s\"\n", path);
	return 0;
}



int myfs_rmdir(const char * path)
{
	log_msg("\n==> rmdir, path = \"%s\"\n", path);
        inode_t* dir = find_inode(path);
        if (NULL == dir)
            return -ENOENT;

	vector<string> dentries;
	parse_dentry(&dentries, dir);
	if(dentries.size() > 2)
	{
		return -EEXIST; 
	}
	
	inode_t * parent_inode = get_inode(dir->parent);
	remove_dentry(parent_inode, dir->name);
	
	blocks[dir->blk_start]->valid = 0; //mark this block as free
	
	vector<inode_t *>::iterator i;
	for(i = inode_table.begin(); i != inode_table.end(); ++i)
	{
		if((*i)->id == dir->id)
		{
			inode_table.erase(i);
			free(dir);
			break;
		}
	}	
	
	log_msg("\n==> rmdir, path = \"%s\"\n", path);

	return 0;
}


int myfs_mkdir(const char * path, mode_t mode)
{
	log_msg("\nmkdir path = \"%s\"\n", path);
	inode_t* newdir = (inode_t *)malloc(sizeof(inode_t));
	if(!newdir)
		return -ENOMEM;

	newdir->id = __get_available_id();

	strcpy(newdir->name, get_filename(path));

	fuse_context* context = fuse_get_context();
	
	memset(&newdir->stbuf, 0, sizeof(struct stat));
	//newdir->stbuf.st_mode = S_IFDIR | 0755;
	newdir->stbuf.st_mode = mode | S_IFDIR;
	newdir->stbuf.st_nlink = 2;

	newdir->stbuf.st_uid = context->uid;
	newdir->stbuf.st_gid = context->gid;
	newdir->stbuf.st_ctime = newdir->stbuf.st_mtime = newdir->stbuf.st_atime = time(0);
	newdir->stbuf.st_blksize = BLOCK_SIZE;
	newdir->stbuf.st_size = BLOCK_SIZE;
	newdir->stbuf.st_blocks = 1;
	newdir->blk_start = get_free_blocks(1);
	sprintf(blocks[newdir->blk_start]->data, ".\n..\n");
	
	inode_table.push_back(newdir);

	char * parent = NULL;
	parent = parent_path(path);
	log_msg("parent: %s\n", parent);
		
	inode_t * parent_inode = find_inode(parent);
	add_dentry(parent_inode, newdir->name);

	newdir->parent = parent_inode->id;
	log_msg("\n<==mkdir path = \"%s\"\n", path);
	return 0;
}

/**
 *  Return the contents of a directory
 */
int myfs_readdir(const char* path, void* buf, fuse_fill_dir_t filler,
                 off_t offset, fuse_file_info* fi)
{
	log_msg("\n==>readdir path \"%s\"\n", path);
//	log_fi(fi);
	assert(fi);
	inode_t * dir = (inode_t *)fi->fh;
	assert(dir);
	assert(S_ISDIR(dir->stbuf.st_mode));

	vector<string> dentries;
	parse_dentry(&dentries, dir);
	
	log_msg("dentries: \n");
	for(unsigned int i = 0; i < dentries.size(); ++i)
		log_msg("%s ", dentries[i].c_str());

	vector<string>::iterator de;
	for(de = dentries.begin(); de != dentries.end(); ++de)
		filler(buf, de->c_str(), &dir->stbuf, 0);
	
	log_msg("\n<==readdir path \"%s\"\n", path);
	return 0;
}

/**
 *  Open a file
 */
int myfs_open(const char* path, fuse_file_info* fi)
{
	log_msg("\n==>open path \"%s\"\n", path);
	fuse_context* context;
	inode_t* file = find_inode(path);

	if (file == NULL)
		return -ENOENT;

	context = fuse_get_context();
	if (context->uid != 0) {
		mode_t rights = my_rights(&file->stbuf, context->uid, context->gid);
		if ((fi->flags & O_RDONLY && !(rights & 4)) ||
				(fi->flags & O_WRONLY && !(rights & 2)) ||
				(fi->flags & O_RDWR && ! ((rights&4)&&(rights&2))))
			return -EACCES;
	}

	fi->fh = (unsigned long)file;
	log_msg("\n<==open path \"%s\"\n", path);
	return 0;
}

/*open the directory*/
/*this function looks up the inode and stores the pointer of this inode as fi*/
int myfs_opendir(const char *path, struct fuse_file_info *fi)
{
	log_msg("\nopendir = \"%s\"\n", path);

	fuse_context* context;
	inode_t* dir = find_inode(path);

	log_msg("\ndir inode = \"%p\"\n", dir);
		
	//this dir inode is not found	
	if (dir == NULL)
		return -ENOENT;

	//test if have the corret permission to open this directory
	context = fuse_get_context();
	if (context->uid != 0) {
		mode_t rights = my_rights(&dir->stbuf, context->uid, context->gid);
		if ((fi->flags & O_RDONLY && !(rights & 4)) ||
				(fi->flags & O_WRONLY && !(rights & 2)) ||
				(fi->flags & O_RDWR && ! ((rights&4)&&(rights&2))))
			return -EACCES;
	}

	//record the pointer of this inode
	fi->fh = (unsigned long)dir;
	
//	log_fi(fi);
	return 0;
}



//Init the inode according the its name and its node
//Currently only the my_init invokes this function to init the root inode
//No others invoke this function
//st_mode type = S_IFREG or S_IFDIR
void init_inode(inode_t * inode, const char * name, mode_t st_mode)
{
	inode->id = __get_available_id();
	fuse_context* context = fuse_get_context();
	cerr << "contextuid = " << context->uid << endl;
	strcpy(inode->name, name);
	memset(&inode->stbuf, 0, sizeof(struct stat));
	inode->stbuf.st_mode = st_mode;
	
	if(S_ISDIR(st_mode))
	{
			//any directory has links at least 2
			inode->stbuf.st_nlink = 2;
			//any directory has only 1 data block
			inode->blk_start = get_free_blocks(1);
			//init this data block...
			sprintf(blocks[inode->blk_start]->data, ".\n..\n");
	}
	else if (S_ISREG(st_mode))
	{
			//any file has link at least 1, starting from 1
			//current version does not support hard links of files
			//so any files can only have link of 1
			inode->stbuf.st_nlink = 1;
			inode->blk_start = get_free_blocks(1);
	}

	else
		assert(0);
			
	inode->stbuf.st_uid = context->uid;
	inode->stbuf.st_gid = context->gid;
	inode->stbuf.st_ctime = inode->stbuf.st_mtime = inode->stbuf.st_atime = time(0);
	inode->stbuf.st_blksize = BLOCK_SIZE;
	inode->stbuf.st_size = BLOCK_SIZE;
	inode->stbuf.st_blocks = 1;
}


//this function is invoked when this file system is mounted
//if we met with any errors in reading the file fuse.fs, we
//start over as if we have never had this file...

void* myfs_init(fuse_conn_info* conn)
{
	log_msg("init!!!!!\n");
	inode_table.clear(); 
	blocks.clear(); 

	log_msg("ready to read file fuse.fs...\n");
	char * buffer = (char*)malloc(sizeof(inode_t) + sizeof(block_t) + sizeof(unsigned long) + 1); 
	
	int readElems;
	
	//read the size of inode_table
	readElems = fread(buffer, sizeof(unsigned long), 1, fusefile);
	if(readElems != 1)
	{
		log_msg("reading error!\n");
		goto new_start;
	}

	//reserve enough space for storing all the inodes
	inode_table.reserve(atol(buffer)); 

	//read all the inode structures in the file
	for (unsigned int i = 0; i < inode_table.capacity(); ++i) 
	{ 
		readElems = fread(buffer, sizeof(inode_t), 1, fusefile); 
		if(readElems != 1)
		{
			log_msg("reading error!\n");
			goto new_start;
		}
		inode_t * temp = (inode_t *)malloc(sizeof(inode_t)); 
		memcpy((char *)temp, buffer, sizeof(inode_t)); 
			
		inode_table.push_back(temp);
		if(strcmp(temp->name, "/") == 0)	//this is the root, so we need to set the global pointer root
			root = temp;	
	} 

	//read the size of blocks
	readElems = fread(buffer, sizeof(unsigned long), 1, fusefile); 
	if(readElems != 1)
	{
		log_msg("reading error!\n");
		goto new_start;
	}

	//reserve enough space for storing blocks
	blocks.reserve(atol(buffer)); 

	//read the block_t structures
	for (unsigned int i = 0; i < blocks.capacity(); ++i) 
	{ 
		readElems = fread(buffer, sizeof(block_t), 1, fusefile); 
		if(readElems != 1)
		{
			log_msg("reading error!\n");
			goto new_start;
		}
		block_t * temp = (block_t *)malloc(sizeof(block_t)); 
		memcpy((char *)temp, buffer, sizeof(block_t)); 
		blocks.push_back(temp); 
	} 

	
	max_inode_id = __find_max_inode_id();	//for __get_available_id to get the correct distinct id number
						//for new allocate inodes in the future
	
	free(buffer);
	return NULL;

new_start:	
	//cannot successfully use the fuse.fs to restore all the file system,
	//so we need to cleanup some already allocated inodes and blocks
	free(buffer);	
	for(auto i = inode_table.begin(); i != inode_table.end(); ++i)
		free(*i);
	for(auto i = blocks.begin(); i != blocks.end(); ++i)
		free(*i);

	inode_table.clear();
	blocks.clear();

	//start out of the blue moon as if we don't have that fuse.fs file
	log_msg("ready to start out of the blue moon...\n");
	info();
	max_inode_id = __find_max_inode_id();

	root = (inode_t *)malloc(sizeof(inode_t));	
	init_inode(root, "/", S_IFDIR | 0755);
	root->parent = -1;			//root does not have a parent
	inode_table.push_back(root);
	return NULL;
}

/**
 *  When we unmount a filesystem, this gets called.
 */
void myfs_destroy (void* state)
{
	log_msg("\ndestroyed!\n");
	log_msg("\nfusefile: %p\n", fusefile);

	fusefile = freopen(NULL, "wb", fusefile);
	rewind(fusefile);

	char * buffer = (char *)malloc(sizeof(inode_t) + sizeof(block_t) + sizeof(unsigned long) + 1); 

	sprintf(buffer, "%lu", (unsigned long)inode_table.size());
//	log_msg("write:%lu\n", atol(buffer));
	fwrite(buffer, sizeof(unsigned long), 1, fusefile); 

	for (auto i = inode_table.begin(), j = inode_table.end(); i != j; i++) 
	{ 
		memcpy(buffer, *i, sizeof(inode_t)); 
		fwrite(buffer, sizeof(inode_t), 1, fusefile); 
	} 

	sprintf(buffer, "%lu", (unsigned long)blocks.size()); 
	fwrite(buffer, sizeof(unsigned long), 1, fusefile); 

	for (auto i = blocks.begin(), j = blocks.end(); i != j; i++) 
	{ 
		memcpy(buffer, *i, sizeof(block_t)); 
		fwrite(buffer, sizeof(block_t), 1, fusefile); 
	} 

	free(buffer); 

	for (auto i = inode_table.begin(), j = inode_table.end(); i != j; i++) 
		free(*i); 

	for (auto i = blocks.begin(), j = blocks.end(); i != j; i++) 
		free(*i); 

	inode_table.clear(); 
	blocks.clear(); 
	dentry_cache.clear();
}

/**
 *  To configure our filesystem, we need to create a fuse_operations struct
 *  that has pointers to all of the functions that we have created.
 *  Unfortunately, when we do this in C++, we can't use easy struct initializer
 *  lists, so we need to make an initialization function.
 */
fuse_operations myfs_ops;
void pre_init()
{
	myfs_ops.init = myfs_init;
	myfs_ops.destroy = myfs_destroy;
	myfs_ops.getattr = myfs_getattr;
	myfs_ops.readdir = myfs_readdir;
	myfs_ops.open = myfs_open;
	myfs_ops.opendir = myfs_opendir;
	myfs_ops.read = myfs_read;
	myfs_ops.mknod = myfs_mknod;
	myfs_ops.mkdir = myfs_mkdir;
	myfs_ops.rmdir = myfs_rmdir;
	myfs_ops.truncate = myfs_truncate;
	myfs_ops.write = myfs_write;
	myfs_ops.utime = myfs_utime;
	myfs_ops.chmod = myfs_chmod;
	myfs_ops.chown = myfs_chown;
	myfs_ops.unlink = myfs_unlink;
	myfs_ops.rename = myfs_rename;
	info();
}

/**
 *  Fuse main can do some initialization, but needs to call fuse_main
 *  eventually...
 */
int main(int argc, char* argv[])
{
	logfile = log_open();    
	fprintf(logfile, "start logging...\n");
	
	if (argc < 2)
		usage();

	fusefile = fopen("fuse.fs", "rb");
	if(!fusefile)
	{
		fprintf(logfile, "cannot find fuse.fs, creating a new one!\n");
		fusefile = fopen("fuse.fs", "wb");
		if(!fusefile)
		{
			fprintf(logfile, "cannot create new fuse.fs...exiting...");
			exit(1);
		}
		fusefile = freopen(NULL, "rb", fusefile);
	}

	log_msg("fusefile: %p\n", fusefile);
	setvbuf(fusefile, NULL, _IOLBF, 0);

	pre_init();

	return fuse_main(argc, argv, &myfs_ops, NULL);
	fclose(fusefile);
}
